package stack.hard;

import java.util.Stack;

/**
 * 柱状图中最大的矩形
 * 示例 1:
 *
 *
 *
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 * 示例 2：
 *
 *
 *
 * 输入： heights = [2,4]
 * 输出： 4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
 */
public class LargestRectangleInHistogram_84 {

    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0)
            return 0;
        if (heights.length == 1)
            return heights[0];
        Stack<Integer> stack = new Stack<>();
        int[] arr = new int[heights.length + 2];
        for (int i = 1; i < heights.length + 1; i++) {
            arr[i] = heights[i - 1];
        }
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                int cur = stack.pop();
                res = Math.max(res, (i - stack.peek() - 1) * arr[cur]);
            }
            stack.push(i);
        }
        return res;
    }

    public static void main(String[] args) {
        LargestRectangleInHistogram_84 lr = new LargestRectangleInHistogram_84();
        System.out.println(lr.largestRectangleArea(new int[]{2,4}));

    }
}
